const { BinarySearchTree } = require('./data-structures/binarySearchTree');
const { defaultCompare, BalanceFactor } = require('./util');

class AVLTree extends BinarySearchTree {
  constructor(compareFn = defaultCompare) {
    super(compareFn);
    this.compareFn = compareFn;
    this.root = null;
  }

  /**
   * 计算一个节点的高度
   * @param {*} node
   * @returns
   */
  getNodeHeight(node) {
    if (node == null) return -1;
    return (
      Math.max(this.getNodeHeight(node.left), this.getNodeHeight(node.right)) +
      1
    );
  }
  /**
   * 遵循计算一个节点的平衡因子
   * @param {*} node
   */
  getBalanceFactor(node) {
    const heightDifference =
      this.getNodeHeight(node.left) - this.getNodeHeight(node.right);
    switch (heightDifference) {
      case -2:
        return BalanceFactor.UNBALANCED_RIGHT;
      case -1:
        return BalanceFactor.SLIGHTLY_UNBALANCED_RIGHT;
      case 1:
        return BalanceFactor.SLIGHTLY_UNBALANCED_LEFT;
      case 2:
        return BalanceFactor.UNBALANCED_LEFT;
      default:
        return BalanceFactor.BALANCED;
    }
  }

  /**
   * 平衡操作-AVL旋转
   * 在对AVL树添加或移除节点后，我们要计算节点的高度并验证树是否需要进行平衡
   * 向AVL树插入节点时，可以执行单旋转或双旋转两种平衡操作
   * 
   * /
  
  /*
   * 左-左（LL）：向右的单旋转：
   * 出现于节点的左侧子节点的高度大于右侧子节点的高度时，
   * 并且左侧子节点也是平衡或左侧较重的
   */
  rotationLL(node){
    const tmp = node.left;
  }
}
